COMMENT ⊗   VALID 00013 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	  Data structures, GSINIT
C00006 00003	  UNLINK, NEWCEL
C00008 00004	  NXTTIM
C00009 00005	  INVLDT
C00011 00006	  CHANGE, CHNGER
C00017 00007	  ADDCHG
C00019 00008	  GETVAL, GETVR0
C00021 00009	  EVALND, EVLEXP
C00029 00010	  MAKEXP, ADDCLC, REMCLC, DELEXP
C00036 00011	  MAKEVN, DELVN
C00043 00012	  MGNDS  marking method for gnodes
C00057 00013	  Known Bugs
C00060 ENDMK
C⊗;
;  Data structures, GSINIT

.SBTTL Graph routines.
;Graph structure definitions
;RHT 9/74  RF 6/75, 10/75

COMMENT ⊗  
This is the runtime's prime evil,
The murderous graph nodes and interlocks.
⊗

;GRAPH NODES		;Common fields for Variables and Expressions
	II==0
	XX  GNMODE	;Mode bits.  1:variable. 2:expression
	XX  NXTGN	;Links all graph nodes.  Points to next one.
	XX  PRVGN	;Previous link in that chain
	XX  INVMRK	;0 => valid, other => invalid
	XX  GNVAL	;points at the value cell
	XX  GNDEPS	;list of dependents (variables or expressions)
	GNEND==II	;marks the end of the common region

;VARIABLE NODES		;Explicitly released, formed from large block store.
	II==GNEND
	XX  VALIDF	;a count which is incremented at every reevaluation
	XX  VNCLCS	;list of expression nodes used as calculators
	XX  VNCHGS	;list of change cells. (see format below)
	VNDSIZ == II/2	;Length of variable node (in words)

;EXPRESSION NODES	;Explicitly released, formed from large block store.
	II==GNEND
	XX  ENISB	;the ISB for this expression
	XX  ENIPC	;the IPC for this expression
	XX  ENNEED	;list of needed nodes (cell-linked)
	ENDSIZ == II/2	;Length of expression node (in words)

;CELL LINKS
	II==0
	XX  CAR	
	XX  CDR	

;CHANGER CELL		;Explicitly released, formed from large block store.
	II==0
	XX  NXTCHG	;next changer cell in chain
	XX  CHGISB	;Points to interpreter status block to resolve addressing
	XX  CHGIPC	;the interpeter PC where the calculation starts
	CHGCSZ == II/2	;Size of changer cell, in words

GNODES:  .BLKW 1	;head of chain of graph nodes.
TIME:	0		;used during evaluation of nodes
GNEVT:	.BLKW 1		;event for interlocking graph references

GSINIT:
;Initialize the graph structure to a null situation;
	EVMAK	;Make a new interlock event.
	MOV (SP),GNEVT;
	EVSIG 	;Give it one signal.
	CLR GNODES;
	CLR TIME;
	RTS PC	;Done

;  UNLINK, NEWCEL

UNLINK:
COMMENT ⊗ A list is in R0, and an entity in R1.  All occurrences of
that entity, if any, are removed from the list.  The orphaned cells
are left for the garbage collector.  A pointer to the list is
returned in R0 (it has changed if the first element was deleted).  ⊗
	MOV R2,-(SP)		;Save R2
	MOV R3,-(SP)		;Save R3
	MOV R0,R2		;R2 ← forward pointer
	BEQ UNL4		;If no list, then done
	MOV R1,-(SP)		;Save R1
	JSR PC,NEWCEL		;R0 ← dummy header
	MOV (SP)+,R1		;Restore R1
	MOV R2,CDR(R0)		;Set up dummy header
	MOV R0,R3		;R3 ← backward pointer
UNL2:	CMP CAR(R2),R1		;Match?
	BEQ UNL1		;Yes
	MOV R2,R3		;
UNL3:	MOV CDR(R2),R2		;Move along
	BNE UNL2		;If any more
	MOV CDR(R0),R0		;Go past dummy
UNL4:	MOV (SP)+,R3		;Restore R3
	MOV (SP)+,R2		;Restore R2
	RTS PC			;Return
UNL1:	MOV CDR(R2),CDR(R3)	;Link past the orphan
	BR  UNL3		;Continue

NEWCEL:
COMMENT ⊗ Returns in R0 a pointer at a cell.  Taken from cell space
unless there is none.  Uses direct jumps, lets the subsidiary do the
return. ⊗
    .IFNZ SMALLB
	MOV #CELSPC,R0	;
	JMP GETSBK	;Allocate from small blocks
    .IFF
	MOV #2,R0	;Number of words needed
	JMP GTFREE	;R0 ← LOC[new block]
    .ENDC
;  NXTTIM

COMMENT ⊗
	JSR	PC,NXTTIM
 	
Returns TIME←TIME+1 in R0.  If TIME goes negative then set all
positive mark cells to negative, then set time to 1. ⊗


NXTTIM:	INC	TIME		;TIME←TIME+1
	MOV	TIME,R0
	BGT	NXT.RT		;OK?
	MOV	GNODES,R0	;
	BEQ	NXTT.3		;DID WE HAVE ANY??
NXTT.1: TST	INVMRK(R0)	;YES
	BLE	NXTT.2		;WAS INVMRK POSITIVE
	NEG	INVMRK(R0)	;YES, NEGATE IT
NXTT.2:	MOV	NXTGN(R0),R0	;GO ON TO NEXT
	BNE	NXTT.1		;IF ANY
NXTT.3:	INC	R0		;R0←0+1
	MOV	R0,TIME		;TIME IS 1 AGAIN
NXT.RT:	RTS	PC

;  INVLDT

ROUTINE INVLDT,<INV.ND>		;Called only from the outside world
	EVWAIT	GNEVT		;We change TIME, so must lock this
	MOV	INV.ND(RF),R1
	JSR	PC,NXTTIM
	MOV	R1,R0
	JSR	PC,INVLR0
	EVSIG	GNEVT		;End of critical section
	RTS	RF

INVLR0:	CMP	INVMRK(R0),TIME	;IS IT DEAD YET?
	BNE	INVL.R		;ALREADY INVALID??
INVL.1:	MOV	TIME,INVMRK(R0)	;NO, MAKE IT SO
	MOV	R2,-(SP)	;SAFE REGISTER
	MOV	GNDEPS(R0),R2	;DEPENDENTS
	BEQ	INVL.X		;IF ANY 
INVL.2:	MOV	CAR(R2),R0	;GET A DEPENDENT
	JSR	PC,INVLR0	;AND INVALIDATE IT
	MOV	CDR(R2),R2	;GO TO NEXT
	BNE	INVL.2		;IF ANY
INVL.X:	MOV	(SP)+,R2	;GET BACK SCRATCH REGISTER
INVL.R:	RTS	PC

;  CHANGE, CHNGER

COMMENT ⊗ Called by the outside world to put a new value, CHG.VNEW,
in the variable node CHG.ND.  Returns with CHG.ND in R0. ⊗

ROUTINE CHANGE,<CHG.ND,CHG.VNEW>
	MOV	R2,-(SP)	;Save R2
	MOV	R3,-(SP)	;Save R3
	MOV	CHG.ND(RF),R1	;R1 ← the target node.
	EVWAIT	GNEVT		;Wait until OK to enter critical code.
	JSR	PC,NXTTIM	;
	MOV	R1,R0		;
	JSR	PC,INVLR0	;invalidate it for the nonce
	MOV	CHG.ND(RF),R0	;R0 ← the target node
	MOV	GNVAL(R0),R2	;R2 ← old value
	MOV	CHG.VNEW(RF),GNVAL(R0) ;stow the new value
	MOV	VNCHGS(R0),R3	;R3 ← list of changers
	BEQ	CH.XXX		;if any
	EVSIG	GNEVT		;Leave the overall graph node critical region.
CH.1:	JSR	PC,CHNGER	;Call the next change routine
	MOV	NXTCHG(R3),R3	;R3 ← next changer
	BNE	CH.1
	EVWAIT	GNEVT		;Enter critical section again.
CH.XXX:	MOV	CHG.ND(RF),R0	;R0 ← the target node
	CLR	INVMRK(R0)	;Revalidate it
	INC	VALIDF(R0)	;Increment its validity count
	EVSIG	GNEVT		;Ok for others to enter critical code now.
	MOV	(SP)+,R3	;Restore R3
	MOV	(SP)+,R2	;Restore R2
	RTS	RF		;Return

CHNGER:
COMMENT ⊗ Calls the change routine indicated.  This is done by
instantiating a new interpreter to do the work.  It should terminate
the normal way, with a TERMINATE command.  R2 points to the old
value, and CHG.VNEW(RF) points to the new value.  R3 points to the
changer cell.  These values are put into the new ISB.  GNODE
exclusion should be released before the call to CHNGER.  Recall that
a changer cell looks like this:
	XX  NXTCHG	;next changer cell in chain
	XX  CHGISB	;Points to interpreter status block to resolve addressing
	XX  CHGIPC	;the interpeter PC where the calculation starts
⊗

	MOV R2,-(SP)	;Save R2
	MOV R3,-(SP)	;Save R3
	MOV R4,-(SP)	;Save R4

	;make a new interpreter to do the work
	MOV CHGISB(R3),R4	;R4 ← ISB we have to emulate
	MOV CHGIPC(R3),R0	;R0 ← IPC of new ISB
	EVMAK		;Stack a new event for communication with subsidiary
	MOV (SP),R1	;R1 ← copy of that event
	JSR PC,SPAWN	;R0 ← Process decriptor
	MOV PDBR4(R0),R4;R4 ← ISB of new interpreter
	MOV R2,OLDV(R4)	;Stow the "old value" pointer in environment.
	MOV CHG.VNEW(RF),NEWV(R4)	;Stow the "new value" pointer.
	FORK R0,#INTERP,#1	;Cause the new process to be started at high prio.

	;clean up after the interpreter
	EVWAIT 		;Wait for the completion event (still on stack)

	MOV (SP)+,R4	;Restore R4
	MOV (SP)+,R3	;Restore R3
	MOV (SP)+,R2	;Restore R2
	RTS PC		;Done
;  ADDCHG

ROUTINE ADDCHG,<ACH.ND,ACH.CHG>
COMMENT ⊗ ACH.ND is the target graph node, and ACH.CHG is a changer
cell all prepared except for the link to the other changers.  It is
necessary to perform this linking.  ⊗
	MOV	R2,-(SP)	;Save R2
	MOV	ACH.ND(RF),R2	;R2 ← LOC[target node]
	MOV	ACH.CHG(RF),R1	;R1 ← LOC[changer cell]
	EVWAIT	GNEVT		;Enter critical region for graph nodes
	MOV	VNCHGS(R2),NXTCHG(R1) ;Link new changer into list
	MOV	R1,VNCHGS(R2)	;
	EVSIG	GNEVT		;Leave critical region
	MOV	(SP)+,R2	;Restore R2
	RTS	R5		;Done
;  GETVAL, GETVR0

COMMENT ⊗ Called by the outside world.  Returns LOC[value(GTV.ND)] in
R0 and the VALIDF in R1, after having scrounged around to get a valid
value, if necessary and possible.  ⊗

ROUTINE GETVAL,<GTV.ND>
	MOV	GTV.ND(RF),R0
	JSR	PC,GETVR0
	RTS	RF

GETVR0:	TST	INVMRK(R0)	;Is the current value good?
	BEQ	GETV.R		;Yes
	EVWAIT	GNEVT		;No.  Enter critical region.
	MOV	R0,-(SP)	;Stack R0
	MOV	RF,-(SP)
	MOV	R0,-(SP)	;EVALNODE(GTV.ND,TIME←TIME+1)
	JSR	PC,NXTTIM	
	MOV	R0,-(SP)
	MOV	#MARK2,-(SP)
	MOV	SP,RF
	JSR	PC,EVALND		
	EVSIG	GNEVT		;Leave critical region
	MOV	(SP)+,R0	;R0 ← target node, now validated
GETV.R:	MOV	VALIDF(R0),R1	;Get the validity count
	MOV	GNVAL(R0),R0	;R0 ← value cell
	RTS	PC		;Done
;  EVALND, EVLEXP

COMMENT ⊗ EVALND is a recursive procedure, which is given EVL.ND, the
target node to evaluate, and EVL.T, the "time" of evaluation.  If
necessary, it calls itself at the same "time" to track down a chain
of related nodes.  GNEVT exclusion should be on before this routine
is first called, and will remain on after the return. ⊗

ROUTINE EVALND,<EVL.ND,EVL.T>
	MOV	EVL.ND(RF),R0	;R0 ← target graph node
	MOV	INVMRK(R0),R1	;Is the node already valid?
	BEQ	EV.RTS		;Yes
	CMP	R1,EVL.T(RF)	;No.  Have we already looked at it this "time"?
	BEQ	EV.RTS		;Yes
	MOV	EVL.T(RF),INVMRK(R0)	;No. We have touched our node now
	MOV	R2,-(SP)	;Save R2
	MOV	R3,-(SP)	;Save R3
	BIT	#1,GNMODE(R0)	;A variable or an expression?
	BNE	EV.TM1		;Variable
	CALL	EVLEXP,<R0,EVL.T>	;Sets GNVAL and INVMRK correctly
	BR	EV.XXX		;Done

EV.TM1:	;evaluate a variable.
	MOV	VNCLCS(R0),R2	;R2 ← list of calculator expressions
	BEQ	EV.XXX		;if any
EV.TM4:	MOV	CAR(R2),R1	;R1 ← first expression
	TST	INVMRK(R1)	;Is this expression valid?
	BNE	EV.TM3		;No
	MOV	GNVAL(R1),GNVAL(R0)	;Yes.  Copy its value pointer
	BR	EV.SUC		;Success exit.
EV.TM3:	MOV	CDR(R2),R2	;R2 ← rest of expression list
	BNE	EV.TM4		;Try with next one.

	;no currently valid expression.  Try to evaluate one.
	MOV	VNCLCS(R0),R2	;R2 ← list of calculator expressions
	BEQ	EV.XXX		;if any
	MOV	CAR(R2),R1	;R1 ← first expression
EV.TM7:	CALL	EVALND,<R1,EVL.T(RF)>
	MOV	CAR(R2),R1	;
	TST	INVMRK(R1)	;Successfully evaluated?
	BEQ	EV.TM6		;Yes
	MOV	CDR(R2),R2	;Try next one
	BNE	EV.TM7		;If any
	BR	EV.XXX		;Give up
EV.TM6:	MOV	EVL.ND(RF),R0	;
	MOV	GNVAL(R1),GNVAL(R0)	;Transfer the value
	BR	EV.SUC		;Success return



	;all the needs are met for the expression in CAR(R2)
	MOV	CAR(R2),R1	;R1 ← expression node
EV.NOK:	CALL	EVALND,<R1,EVL.T(RF)>	;Evaluate the expression.
	MOV	EVL.ND(RF),R0	;R0 ← target node
	MOV	GNVAL(R1),GNVAL(R0)	;Stow away its new value.
EV.SUC:	CLR	INVMRK(R0)	;Mark it as valid.
	INC	VALIDF(R0)	;Increment its validity number
EV.XXX:	MOV	(SP)+,R3	;Restore R3
	MOV	(SP)+,R2	;Restore R2
EV.RTS:	RTS	RF		;Done

COMMENT ⊗ Each expression has a field, ENISB, which points to the
interpreter status block of its definition.  This contains enough
information to resolve any variable references in the expression.
Calls the interpreter in a special way (through a CALL INTERP) having
first set up a pseudo-ISB in R4.  When the interpreter returns, the
desired value should be in R0.  Each time called, this routine
constructs a new pseudo-ISB, uses it once, and then releases it.
This is somewhat wasteful, and could be cleaned up.  The value found
is put in the expression node, which is marked as valid.  It is not
assumed that all the needed nodes have been validated before this
routine is called.  ⊗

ROUTINE EVLEXP,<EVE.EXP,EVE.T>
	MOV	R2,-(SP)	;Save R2
	MOV	R3,-(SP)	;Save R3
	MOV	R4,-(SP)	;Save R4

	;try to validate the needed list
	MOV	EVE.EXP(RF),R0	;R0 ← LOC[ENODE]
	MOV	EVE.T(RF),INVMRK(R0)	;We are looking now.
	MOV	ENNEED(R0),R3	;R3 ← needed list
	BEQ	EVE.L2		;if any
EVE.L3: CALL	EVALND,<CAR(R3),EVL.T(RF)>	;Evaluate this need.
	MOV	CAR(R3),R0	;R0 ← variable node of the need
	TST	INVMRK(R0)	;Is it now valid?
	BNE	EVE.FF		;No, so we fail
	MOV	CDR(R3),R3	;Yes.  R3 ← next needed cell
	BNE	EVE.L3		;If any.

	;the needed list is ready
EVE.L2:	MOV	#ISBS,R0	;Get a pseudo-ISB
	JSR	PC,GTFREE	;R0 ← LOC[new ISB]
	MOV	R0,R4		;R4 ← LOC[new ISB]
	MOV	EVE.EXP(RF),R2	;
	MOV	ENISB(R2),R1	;R1 ← LOC[old ISB]
	MOV	ENV(R1),ENV(R4)	;Copy environments
	MOV	LEV(R1),LEV(R4)	;Copy levels
	MOV	ENIPC(R2),IPC(R4)	;Initialize the IPC
	MOV	#INSTSZ,R0	;
	JSR	PC,GTFREE	;R0 ← LOC[new interpreter stack]
	MOV	R0,-(SP)	;Save the stack location
	ADD	#INSTSZ,R0	;
	MOV	R0,R3		;R3 ← LOC[verge of new interpreter stack]
	INC	GCOK		;Don't garbage collect during this.
	CALL	INTERP		;Enter the interpreter, R0 ← LOC[new value cell]
	DEC	GCOK		;Garbage collect ok now.
	MOV	R0,R2		;R2 ← LOC[new value cell]
	MOV	R4,R0		;Release the ISB
	JSR	PC,RLFREE	;
	MOV	(SP)+,R0	;Release the interpreter stack
	JSR	PC,RLFREE	;
	MOV	EVE.EXP(RF),R0	;R0 ← LOC[expression node]
	CLR	INVMRK(R0)	;Now valid
	MOV	R2,GNVAL(R0);Result into the node
EVE.FF:	MOV	(SP)+,R4	;Restore R4
	MOV	(SP)+,R3	;Restore R3
	MOV	(SP)+,R2	;Restore R2
	RTS	RF		;Return
;  MAKEXP, ADDCLC, REMCLC, DELEXP

ROUTINE ADDCLC,<ADD.VN,ADD.EN>
COMMENT ⊗ ADD.VN is the variable node, and ADD.EN is an expression
node all prepared except for the link to the variable node.  This
linking is performed.  ⊗
⊗
	MOV	R2,-(SP)	;Save R2
	MOV	R3,-(SP)	;Save R3
	MOV	ADD.VN(RF),R2	;R2 ← LOC[variable node]
	MOV	ADD.EN(RF),R3	;R3 ← LOC[expression node]
	EVWAIT	GNEVT		;Enter critical region
	;Add the VNODE as a dependent of the ENODE
	JSR	PC,NEWCEL	;R0 ← LOC[new cell]
	MOV	GNDEPS(R3),CDR(R0)
	MOV	R2,CAR(R0)	;
	MOV	R0,GNDEPS(R3)	;
	;Add the ENODE as an expression of the VNODE
	JSR	PC,NEWCEL	;R0 ← LOC[new cell]
	MOV	VNCLCS(R2),CDR(R0)
	MOV	R3,CAR(R0)	;
	MOV	R0,VNCLCS(R2)	;
	EVSIG	GNEVT		;Leave critical region
	MOV	(SP)+,R3	;Restore R3
	MOV	(SP)+,R2	;Restore R2
	RTS	RF		;Done

ROUTINE MAKEXP,<MKE.ISB,MKE.IPC,MKE.NDS>
COMMENT ⊗ Makes a new expression node with ENISB, ENIPC, ENNDS as
specified.  Makes it a dependent of all the variables on the needed
list.  ⊗

	MOV R2,-(SP)		;Save R2
	MOV R3,-(SP)		;Save R3
	MOV #ENDSIZ,R0		;
	JSR PC,GTFREE		;
	MOV R0,R3		;R3 ← LOC[new expression node]
	MOV #2,GNMODE(R3)	;Expression
	MOV #-1,INVMRK(R3)	;Invalid
	CLR GNVAL(R3)		;No value
	CLR GNDEPS(R3)		;No variable dependents
	MOV MKE.ISB(RF),ENISB(R3)	;ISB
	MOV MKE.IPC(RF),ENIPC(R3)	;IPC
	MOV MKE.NDS(RF),R2	;Need list
	EVWAIT GNEVT		;Enter critical region
	MOV R2,ENNEED(R3)	;

	;this expression is a dependent for each variable on the needed list.
	BEQ MKE2		;If any
MKE1:	JSR PC,NEWCEL		;
	MOV CAR(R2),R1		;R1 ← the next needed variable
	MOV GNDEPS(R1),CDR(R0)	;
	MOV R3,CAR(R0)		;
	MOV R0,GNDEPS(R1)
	MOV CDR(R2),R2		;
	BNE MKE1		;Repeat

MKE2:	;link up with all other graph nodes in the world
	MOV GNODES,R1		;
	BEQ MKE3		;If any
	MOV R1,NXTGN(R3)	;
	MOV R3,PRVGN(R1)	;
MKE3:	MOV R3,GNODES		;
	MOV R3,R0		;R0 ← LOC[new expression node]
	EVSIG GNEVT		;Leave critical region
	MOV (SP)+,R3		;Restore R3
	MOV (SP)+,R2		;Restore R2
	RTS RF			;Done

ROUTINE REMCLC,<RMC.VN,RMC.EN>
COMMENT ⊗ Unlinks the given expression from the given variable.  ⊗
	MOV R2,-(SP)		;Save R2
	MOV R3,-(SP)		;Save R3
	MOV RMC.EN(RF),R2	;R2 ← ENODE
	MOV RMC.VN(RF),R3	;R3 ← VNODE
	CALL GETVAL,<R3>	;Make sure he has a last chance to get value.
	EVSIG GNEVT		;Enter critical region
	;remove the VNODE as a dependent of the ENODE
	MOV GNDEPS(R2),R0	;
	MOV R3,R1		;
	JSR PC,UNLINK		;
	MOV R0,GNDEPS(R2)	;
	;remove the ENODE as a calculator of the VNODE
	MOV VNCLCS(R3),R0	;
	MOV R2,R1		;
	JSR PC,UNLINK		;
	MOV R0,VNCLCS(R3)	;
	EVSIG GNEVT		;Leave critical region
	MOV (SP)+,R3		;Restore R3
	MOV (SP)+,R2		;Restore R2
	RTS RF			;Done

ROUTINE DELEXP,<DLE.EN>
COMMENT ⊗ Must remove this expression from all variable nodes which
are dependent on it, having tried to validate them.  Then unlink the
expression node and reclaim it.  ⊗
	MOV R2,-(SP)		;Save R2
	MOV R3,-(SP)		;Save R3
	MOV DLE.EN(RF),R2	;R2 ← LOC[victim expression node]
	EVWAIT GNEVT		;Enter critical region
	MOV GNDEPS(R2),R3	;R3 ← list of dependents
	BEQ DLE1		;If any
	JSR PC,NXTTIM		;
	MOV R0,-(SP)		;New time for the evaluations to follow
DLE2:	MOV CAR(R3),R0		;
	MOV (SP),R1		;Time
	CALL EVALND,<R0,R1>	;Try to validate him
	MOV VNCLCS(R0),R0	;R0 ← his list of calculators
	MOV R2,R1		;us
	JSR PC,UNLINK		;Remove us from that list
	MOV CAR(R3),R1		;him
	MOV R0,VNCLCS(R1)	;Put back his calculator list, minus us.
	MOV CDR(R3),R3		;Next calculator
	BNE DLE2		;If any
	TST (SP)+		;Clear the time from the stack

	;unlink this expression node
DLE1:	MOV NXTGN(R2),R1	;R1 ← forward link
	MOV PRVGN(R2),R0	;R0 ← backward link
	MOV R0,PRVGN(R1)	;
	MOV R1,NXTGN(R0)	;
	EVSIG GNEVT		;Leave critical region.
	MOV (SP)+,R3		;Restore R3
	MOV (SP)+,R2		;Restore R2
	RTS RF			;Done
	
;  MAKEVN, DELVN

MAKEVN:
COMMENT ⊗ Creates a variable node, with no frills (no calculators,
changers, loksh, boydem, tsibele, ...) except that if R0 is
non-zero, that is assumed to be the value cell pointer.  The node
will be marked as invalid unless there was some value given.  The
space is taken from large block storage.  The new variable node is
returned in R0.  ⊗

	MOV R0,-(SP)	;Save R0
	MOV #VNDSIZ,R0	;
	JSR PC,GTFREE	;R0 ← LOC[new graph node]
	CLR INVMRK(R0)	;Validate the node
	MOV #1,GNMODE(R0)	;Variable, not expression
	MOV (SP)+,GNVAL(R0)	;Stuff away the value cell pointer.
	BNE MKVN2	;Was there one?
	MOV #-1,INVMRK(R0)	;No. Invalidate this node.
MKVN2:	CLR GNDEPS(R0)	;Zero other fields
	CLR VNCLCS(R0)	;
	CLR VNCHGS(R0)	;
	CLR NXTGN(R0)	;
	CLR PRVGN(R0)	;
	CLR VALIDF(R0)	;
	EVWAIT GNEVT	;Critical section here
	MOV GNODES,R1	;Link up to other nodes in the world.
	BEQ MKVN1	;If any
	MOV R1,NXTGN(R0);
	MOV R0,PRVGN(R1);
MKVN1:	MOV R0,GNODES	;
	EVSIG GNEVT	;End of critical section
	RTS PC		;

DELVN:
COMMENT ⊗ R0 is the location of the variable node.  All dependent
expressions are first validated if possible, then those are deleted.
The value cell and all cell lists (like GNDEPS, VNCLCS) are reclaimed
by relying on the garbage colector.  Thus graph nodes may share value
cells.  The changer list is explicitly released, so changer lists may
not be shared.  Then the node itself is unlinked from the chain and
returned to free storage. ⊗

	MOV R2,-(SP)		;Save R2
	MOV R3,-(SP)		;Save R3
	MOV R0,R2		;R2 ← variable node to delete

	;Try to validate the dependents
	MOV GNDEPS(R2),R3	;R3 ← List of dependent expressions
	BEQ DEL3		;if any
	JSR PC,NXTTIME		;R0 ← next "time"
	MOV R0,-(SP)		;Save "time"
DEL2:	MOV (SP),R0		;Validate all dependents with this "time".
	CALL EVALND,<CAR(R3),R0>;Evaluate one expression
	CALL DELEXP,<CAR(R3)>	;Delete expression.
	MOV CDR(R3),R3		;R3 ← next dependent
	BNE DEL2		;if any
	TST (SP)+		;clean time off stack

	;Tell each calculator expression that we are no longer dependent
DEL3:	EVWAIT GNEVT		;Enter critical region
	MOV VNCLCS(R2),R3	;R3 ← List of calculator expressions
	BEQ DEL4		;If any
DEL5:	MOV CAR(R3),R0		;
	MOV GNDEPS(R0),R0	;R0 ← that expression's dependent list
	MOV R2,R1		;R1 ← us
	JSR PC,UNLINK		;Remove us from his dependent list
	MOV CAR(R3),R1		;R1 ← him
	MOV R0,GNDEPS(R1)	;Replace his new dependent list
	MOV CDR(R3),R3		;Do the same for the other calculator expressions
	BNE DEL5		;If any

	;Reclaim the changer cells
DEL4:	MOV VNCHGS(R2),R3	;R3 ← First changer cell
DEL6::	MOV R3,R0		;R0 ← current changer cell
	BEQ DEL7		;If any
	MOV NXTCHG(R3),R3	;R3 ← next changer cell
	JSR PC,RLFREE		;Release current one
	BR  DEL6		;Do the others

	;Unlink this graph node
DEL7:	MOV NXTGN(R2),R1	;R1 ← forward link
	MOV PRVGN(R2),R0	;R0 ← backward link
	MOV R0,PRVGN(R1)	;
	MOV R1,NXTGN(R0)	;
	EVSIG GNEVT		;Leave critical region.

	MOV R2,R0		;R0 ← target graph node hulk
	JSR PC,RLFREE		;Release it.
	MOV (SP)+,R3		;Restore R3
	MOV (SP)+,R2		;Restore R2
	RTS PC			;Done

;  MGNDS  marking method for gnodes

MGNDS:	;Marking method for GNODES
	MOV R2,-(SP)		;Save R2
	EVWAIT GNEVT		;Enter critical region
	MOV GNODES,R2		;R2 ← LOC[first graph node]
	BEQ MGNDS1		;If none, then done
MGNDS2:	MOV GNVAL(R2),R0	;Mark the value cell
	JSR PC,MARKQ		;
	MOV R0,GNVAL(R2)	;Put it back (compactification may move it)
	MOV GNDEPS(R2),R0	;Mark the cells used in the dependent list
	JSR PC,MCELL		;
	MOV R0,GNDEPS(R2)	;Put it back
	BIT #1,GNMODE(R2)	;What kind of graph node is it?
	BEQ MGNDS4		;
	MOV VNCLCS(R2),R0	;A variable.  Mark cells in CLC list
	JSR PC,MCELL		;
	MOV R0,VNCLCS(R2)	;Put it back
	BR  MGNDS3		;
MGNDS4:	MOV ENNEED(R2),R0	;An expression.   Mark cells in ENNEED list
	JSR PC,MCELL		;
	MOV R0,ENNEED(R2)	;Put it back
MGNDS3:	MOV NXTGN(R2),R2	;R2 ← LOC[next graph node]
	BNE MGNDS2		;Repeat as necessary
MGNDS1:	MOV (SP)+,R2		;Restore R2
	EVSIG GNEVT		;Leave critical region
	RTS RF			;Return
;  Known Bugs

COMMENT ⊗ It is possible that while a graph node is changed, a
changer is invoked.  During its execution, some other process
modifies the change list for that node.  When the changer is done, it
may get lost in the changer cell list.  Graph node exclusion must be
turned off during execution of a changer, so that it can change other
cells.  Special changer exclusion causes deadlock in the case that
one changer triggers another.  

Certain variables, like YELLOW and BLUE, are not being initialized
to anything.

When a variable goes away, calculators depending on it are
not being destroyed, even though they are unlinked
from anyone who uses them.
⊗